/*
 * @Author: your name
 * @Date: 2021-10-04 16:11:49
 * @LastEditTime: 2021-10-05 11:13:25
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \luogu\1.2排序\模板\插入排序\直接插入排序\mian.cpp
 */
#include<iostream>
using namespace std;

const int LENGTH = 7;

//普通插入排序
void insertSort(int array[],int n);

//简单优化插入排序
void insertSort2(int array[],int n);

//折半插入排序 减少比较次数
void BInsertSort(int a[],int n);

int main(){
    int a[LENGTH] = {0,2,6,4,2,1,5};
    cout << "init data:" << endl;
    for(int i=1; i<LENGTH; i++){
        cout << a[i] << " ";
    }
    cout << endl;
    // insertSort(a,LENGTH);
    // insertSort2(a,LENGTH);
    BInsertSort(a,LENGTH);
    for(int i=1; i<LENGTH; i++){
        cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}

void insertSort(int array[],int n)
{
    for(int i=2; i<n; i++){
        array[0] = array[i];
        for(int j=i-1; j>=0; j--){
            if(array[j] > array[0]){
                array[j+1] = array[j];
            }else{
                array[j+1] = array[0];
                break;
            }
        }
    }
}

void insertSort2(int array[],int n)
{
    for(int i=2; i<n; i++){
        if(array[i] < array[i-1]){
            //哨兵
            array[0] = array[i];
            int j;
            for(j=i-1; array[j] > array[0]; j--){
                array[j+1] = array[j];
            }
            array[j+1] = array[0];
        }
    }
}

void BInsertSort(int a[],int n)
{
    for(int i=2; i<n; i++){
        if(a[i] < a[i-1]){
            a[0] = a[i];
            //二分查找第一个小于a[i]的值
            int left = 1;
            int right = i-1;
            while(left < right){
                //这里等于的话要找右边界,会输出第一个小于a[0]的值下标
                int mid = (left+right+1)/2; //右开
                if(a[0] < a[mid]){
                    right = mid-1;
                }else{
                    left = mid;
                }
            }
            //加个越界判断,没办法了,又不能使用(l+r)/2
            if(a[0] < a[left]){
                left--;
            }

            cout << "farray:";
            for(int k=1; k<i; k++){
                cout << a[k] << ' ';
            }
            cout << "find num:" << a[0] << " out index:" << left << endl; 


            //left 第一个小于a[0]的值下标 left+1 到 i-1 统统后移
            for(int j=i-1; j>=left+1; j--){
                a[j+1] = a[j];
            }
            //a[0]归位
            a[left+1] = a[0];
        }
    }
}